1. Field of the Invention
The invention relates to high efficiency data compression including packet header compression.
2. Description of the Prior Art
There are many areas where it is critical to be able to compress a sequence of values, in an manner that is efficient and robust to errors. An example is IP/UDP/RTP header compression to carry real-time IP-based multi-media traffic over cellular networks. Due to the large size of the IP/UDP/RTP header and the bandwidth limitations of cellular systems, compression efficiency is a must. Error robustness is also required due to the error-prone characteristics of the cellular link.
The RTP header compression described in Internet Engineering Task Force (IETF) RFC 2508, February 1999, achieves high compression efficiency on a lossless compressor-decompressor link. It can compress most of the headers to as low as two bytes. However, this scheme is not robust to errors. The problems encountered are error propagation and increased compressed header sizes. Error propagation refers here to the fact that if a compressed header is hit by an error, not only is this compressed header not decodable but the following compressed headers will likely not be decodable even though they are error free. Increased compressed header size refers here to the fact that because of the error recovery procedure, compressed headers on a lossy link are larger than the optimal 2 bytes achieved on a lossless link. Limitations of RFC 2508 are hereinafter discussed.
Header compression schemes take advantage of the fact that certain information fields carried in the headers either 1.) do not change (called here xe2x80x98Type 1xe2x80x99 header fields) or 2.) change in a fairly predictable way (called here xe2x80x98Type 2xe2x80x99 header fields). Other fields, referred to as xe2x80x98Type 3xe2x80x99 header fields, vary in such a way that they cannot be truly predicted.
Examples of Type 1 header fields are the IP address, UDP port number, RTP SSRC (synchronization source), etc. These fields need only be transmitted to the receiver/decompressor once during the course of a session (as part of the packet(s) transferred at session establishment, for example).
Examples of Type 2 header fields are the RTP time stamp, RTP sequence number, and IP ID fields. All have a tendency to increment by some constant amount from packet to packet. Thus, there is no need for these values to be transmitted within every header. It is only required that the decompressor be made aware of the constant increment (differential) value, called delta in RFC 2508. The decompressor utilizes these deltas to regenerate up-to-date Type 2 field values when reconstructing the original header. In other words, differential encoding is used to compress type 2 header fields.
The IP-ID field for most of IP stack implementations increments by a fixed amount for every packet sent by the source. Therefore as long as an RTP stream packets are not interleaved with other packets from the same source on the compressor-decompressor (CD)-channel, the IP-ID delta is constant and does not need to be transmitted.
An Example of a Type 3 header field is the RTP M-bit (Marker), which indicates the occurrence of some boundary in the media (e.g., end of a video frame). Because the media normally varies in unpredictable ways, this information cannot be truly predicted.
The above mentioned limitations of header compression schemes stem from the delta encoding used for type 2 fields. Because of differential encoding, if a single compressed header is lost, all the following compressed headers are not decodable because they are recursively predicted from a compressed header which is not decodable. This is what we called error propagation.
An algorithm used to recover from error propagation is known as the xe2x80x9ctwicexe2x80x9d algorithm which can be used if the packet UDP checksum is transmitted in the compressed packet. Compressed packets on the CD-link carry a 4-bit sequence number which is incremented by one for each compressed packet sent by the compressor. The decompressor uses this sequence number to detect compressed packet loss on the link. If the sequence number increases by more than one, the decompressor hopes that all the compressed packet deltas have not changed since the last compressed packet delta and add one delta for each lost packet. The decompressor checks then that the assumption was valid by computing the decompressed packet UDP checksum and checking if it matches the transmitted UDP checksum.
The twice algorithm is too limiting. First, it requires transmission of the checksum (2 bytes) in every compressed packet and thus significantly reduces the compression efficiency. Second, for a typical audio stream, the twice algorithm works only if there has not been any TS or IP-ID jumps since the last decompressed packet.
When the decompressor is not able to decompress a packet, it sends an negative acknowledgment Nack to the compressor. Upon reception of Nack, the compressor has to send uncompressed header fields. The Nack mechanism thus incurs audio or video outages of a duration of at least one round-rip delay and decreased compression efficiency, since fields have to be sent uncompressed.
In order to limit error propagation, the compressor may use a refresh mechanism whereby it sends periodically uncompressed field values even though this is not requested by the decompressor. However such a mechanism further decreases compression efficiency.
Another limitation of RFC 2508 is the compressed header short sequence number. When the decompressor receives a header with a sequence number that is not consecutive from the previous one, packet loss is detected and a recovery scheme is employed to resynchronize the compressor and decompressor. Just using a short sequence number to detect packet loss is not robust to an error-prone link, such as wireless where xe2x80x98long lossxe2x80x99 may happen frequently. Long loss is defined as the loss of xe2x80x98sequence cyclexe2x80x99 or more packets in a row. When long loss occurs, the sequence number in the packet received by decompressor xe2x80x98wraps aroundxe2x80x99. For example, assume the sequence number consists of k bits, hence the sequence cycle equals to 2k. If 2k packets are lost in a row, the decompressor fails to detect the packet losses since it still sees a consecutive sequence number in the incoming packets.
The invention is a robust and efficient encoding scheme which in one embodiment is referred to as VLE (variable length encoding). VLE and other embodiments of the invention solve the error propagation and efficiency drop of the prior art.
The invention is based in part on the observation, that header type 2 fields received at the compression point show an increasing trend. This implies that fields from consecutive headers tend to have the same MSBs (most significant bits) and differ only by their LSBs (least significant bits). Compression can thus be achieved by transmitting only the LSBs.
The invention allows the compressor to determine the minimum number of LSBs to be sent such that this number is sufficient to allow correct decompression whenever the loss occurs of previous compressed packets on the CD-link.
The invention can be applied to any series of values. The more clustered (i.e. close to each other) the values, the higher the efficiency.
A method of compressing a current value into a minimum number of bits for transmission from a compressor to a decompressor in accordance with the invention includes maintaining a series of at least one previous value at the compressor, each previous value having different k least significant bits and which have been transmitted to the decompressor; determining a value of k representing a smallest number of bits which allows successful decompression of the current value at the decompressor using as a reference value any value in the series of previous values; and transmitting the current value from the compressor to the decompressor in compressed form with the k least significant bits of the current value. The value of k may be determined by comparing the current value with the previous values to determine a maximum difference r between the current value and the previous values with k being an integer chosen to be the smallest integer which is greater than log2(r)+1. The decompressor may transmit at least one acknowledgment to the compressor which indicates that the decompressor has decompressed a value and the compressor may update the series of at least one previous value to discard an older at least one previous value. The decompressor may decompress the current value with a reference value of a last value of the series of at least one previous value to be decompressed as a value having k least significant bits identical to the k least significant bits of the received current value which is closest to the reference value. The decompressor may use a search interval which contains values which range from less than to greater than the reference value; and may choose from the values within the search interval the value having the identical k least significant bits. The values may be produced from mapping a reference value v_ref and the number of bits k to the series of at least one previous value and the current value; and the series of at least one previous value may be updated to have as an oldest value an oldest transmitted value which has been acknowledged to have been decompressed by the decompressor. The values may be a function of a reference value and the number of bits k. The function may be ]v_refxe2x88x922kxe2x88x921, v_ref+2kxe2x88x921]. The function may be ]v_ref, v_ref+2k]. The at least one acknowledgment may be the received uncompressed or compressed value. The at least one acknowledgment may be the received compressed value including information used in coding a portion of the compressed value. The at least one acknowledgment may contain an oldest value in the series of the at least one previous value. The series of at least one previous value may be updated to discard older previous values based upon an estimated maximum number of values which can be lost during transmission in a sequence of values between the compressor and the decompressor. The compressed current value may encode the number k which is transmitted with the current value. The encoding may be Huffman encoding. The values may comprise RTP headers. The at least one acknowledgment may be an acknowledgment of an RTP SN header representing an acknowledgment of TS and IP-ID in the RTP header.
A system for compressing a current value into a minimum number of bits in accordance with the invention includes a compressor which maintains a series of at least one previous value, each previous value having different k least significant bits; a decompressor which receives the current value compressed into a minimum number of k least significant bits from the compressor; and wherein the compressor determines a value of k representing a smallest number of bits which allows successful decompression of the current value at the decompressor using as a reference any value in the series of at least one previous value. The value of k may be determined by comparing the current value with the at least one previous value to determine a maximum difference r between the current value and the at least one previous value with k being an integer chosen to be the smallest integer which is greater than log2(r)+1. The decompressor may transmit at least one acknowledgment to the compressor which indicates that the decompressor has decompressed a value and the compressor may update the series of at least one previous value to discard an older at least one previous value. The decompressor may decompress the current value at the decompressor with a reference value of a last value of the series of at least one previous value to be decompressed as a value having k least significant bits identical to the k least significant bits of the received current value which is closest to the reference value. The decompressor may use a search interval which contains values which range from less than to greater than the reference value; and may choose from the values within the search interval the value having the identical k least significant bits. The compressor may produce the values from mapping a reference value v_ref and the number of bits k to the series of at least one previous value and the current value; and the series of at least one previous value may be updated to have as an oldest value an oldest transmitted value which has been acknowledged to have been decompressed by the decompressor. The function may be ]v_refxe2x88x922kxe2x88x921, v_ref+2kxe2x88x921]. The function may be ]v_ref, v_ref+2k]. The acknowledgments may be the received uncompressed value. The at least one acknowledgment may be the received compressed value. The at least one acknowledgment may be the received compressed value including information used in coding a portion of the compressed value. The series of at least one previous value may be updated by the compressor to discard at least one older previous value based upon an estimated maximum number of values which can be lost during transmission in a sequence of values between the compressor and the decompressor. The compressed current value may encode the number k which is transmitted with the current value. The values may comprise RTP headers. The at least one acknowledgment may be an acknowledgment of an RTP SN header representing an acknowledgment of TS and IP-ID in the RTP header.